package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 2466. 统计构造好字符串的方案数
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/14 17:03
 */
public class CountGoodStrings {

    public static void main(String[] args) {
        CountGoodStrings test = new CountGoodStrings();

        // 8
        int low = 3;
        int high = 3;
        int zero = 1;
        int one = 1;

        // 5
//        int low = 2;
//        int high = 3;
//        int zero = 1;
//        int one = 2;

        int i = test.countGoodStrings(low, high, zero, one);
        System.out.println(i);
    }

    public int countGoodStrings(int low, int high, int zero, int one) {
        long[] arr = new long[high + 1];
        arr[zero]++;
        arr[one]++;
        for (int i = Math.min(zero, one); i < high; i++) {
            long l = arr[i];
            if (i + zero <= high) {
                arr[i + zero] = (arr[i + zero] + l) % 1000000007;
            }
            if (i + one <= high) {
                arr[i + one] = (arr[i + one] + l) % 1000000007;
            }
        }
        long sum = 0;
        for (int i = low; i <= high; i++) {
            sum += arr[i];
        }
        return (int) (sum % 1000000007);
    }

}
